package test.algorithm;

import org.junit.Test;

import java.awt.*;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * 马踏棋盘游戏
 * 
 * @author 延晓磊
 *
 * @since 2020年7月31日
 */
public class HorseChessboard {

	// 棋盘的X轴方格数（横）
	private int x;
	// 棋盘的Y轴方格数（竖）
	private int y;
	// 棋盘
	private int[][] chessboard;
	// 棋盘访问标识
	private boolean[] visited;
	// 完成标识
	private boolean finished;
	
	@Test
	public void test() {
		play(8, 8, 4, 4);
	}
	
	/**
	 * 开始游戏
	 * 
	 * @param x			棋盘的X轴方格数
	 * @param y			棋盘的Y轴方格数
	 * @param startX	马起始位置-X轴
	 * @param startY	马起始位置-Y轴
	 * @return 棋盘
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月31日
	 */
	public static HorseChessboard play(int x, int y, int startX, int startY) {
		// 创建棋盘
		HorseChessboard board = new HorseChessboard();
		board.x = x;
		board.y = y;
		board.chessboard = new int[x][y];
		board.visited = new boolean[x * y];
		// 移动
		long start = System.currentTimeMillis();
		board.traversalChessboard(startX, startY, 1);
		// 结果展示
		System.out.println("游戏时间：" + (System.currentTimeMillis() - start) + "毫秒");
		board.show();
		return board;
	}
	
	/**
	 * 是否完成
	 * 
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月31日
	 */
	public boolean isFinished() {
		return finished;
	}
	
	/**
	 * 棋盘
	 * 
	 * @return	[X轴/列][Y轴/行]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月31日
	 */
	public int[][] getChessboard() {
		return chessboard;
	}

	/**
	 * 显示
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月31日
	 */
	public void show() {
		System.out.println("游戏结果：" + (finished ? "成功" : "失败"));
		// 棋盘步骤
		for (int[] rows : chessboard) {
			for (int step : rows) {
				System.out.print(step + "\t");
			}
			System.out.println();
		}
	}

	/**
	 * 遍历棋盘
	 *
	 * @param row	马的位置-X轴
	 * @param col	马的位置-Y轴
	 * @param step	当前步数
	 */
	private void traversalChessboard(int row, int col, int step) {
		// 棋盘 - 步数
		chessboard[row][col] = step;
		// 访问位置
		visited[row * x + col] = true; 
		// 获取当前位置的可移动位置
		List<Point> ps = next(new Point(row, col));
		// 排序：优先探测深度小的位置，以减少递归回溯的次数（通过贪心算法进行优化）
		ps.sort(Comparator.comparingInt(p -> next(p).size()));
		// 递归回溯
		Point p = null;
		while (!ps.isEmpty()) {
			// 探测
			p = ps.remove(0);
			if (!visited[p.x * x + p.y]) {
				traversalChessboard(p.x, p.y, step + 1);
			}
		}
		// 探测完成
		if (step < x * y && !finished) {
			// 探测失败，悔棋
			chessboard[row][col] = 0;
			visited[row * x + col] = false;
		} else {
			// 探测成功
			finished = true;
		}
	}

	/**
	 * 计算可移动位置（根据日字规则定位，最多8个）
	 * 
	 * @param curPoint	当前位置
	 * 
	 * @return [可移动位置]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月31日
	 */
	private List<Point> next(Point curPoint) {
		// 根据日字规则，在当前位置的周围确定可移动位置，不能超出棋盘，最多会的8个
		List<Point> ps = new ArrayList<>();
		Point p = new Point();
		if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y - 1) >= 0) {
			// 左上
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) {
			// 上左
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x + 1) < x && (p.y = curPoint.y - 2) >= 0) {
			// 上右
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x + 2) < x && (p.y = curPoint.y - 1) >= 0) {
			// 右上
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x + 2) < x && (p.y = curPoint.y + 1) < y) {
			// 右下
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x + 1) < x && (p.y = curPoint.y + 2) < y) {
			// 下右
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < y) {
			// 下左
			ps.add(new Point(p));
		}
		if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < y) {
			// 左下
			ps.add(new Point(p));
		}
		return ps;
	}

}
